//逆拓扑排序和拓扑排序正好相反，一个是处理出度为0，一个是处理入度为0。值得注意的是，逆拓扑序列和拓扑序列正好相反！
//这里使用DFS来实现逆拓扑排序。

#include "MGraph.h" //邻接链表
#include <iostream>

using namespace std;

bool visited[MaxVertexNum];
int print[MaxVertexNum];
int count = 0;

void DFS(MGraph G, int v) //这里相当于树的后根遍历
{
    visited[v] = true;                                                   //标记已访问
    for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) //递归未被访问的邻接结点w
    {
        if (!visited[w])
            DFS(G, w);
    }
    print[count++] = v; //相当于visit操作，记录逆拓扑排序序列
    return;
}

void DFSTraverse(MGraph G) //找到所有起点开始递归
{
    for (int i = 0; i < G.vexnum; i++) //初始化所有visited数组
        visited[i] = false;
    for (int v = 0; v < G.vexnum; v++) //从v = 0结点开始递归
        if (!visited[v])
            DFS(G, v);
    return;
}

int main()
{
    MGraph G;
    G.DirStatue = 1; //有向图，且不带权
    cout << "input vexnum and arcnum:\n";
    cin >> G.vexnum >> G.arcnum; //确认该图顶点数和边数
    Init(G);                     //初始化图G

    //得到该图的邻接矩阵
    cout << "please input (x y):\n";
    for (int x, y, i = 0; i < G.arcnum; ++i)
    {
        cin >> x >> y;
        AddEdge(G, x, y);
    }

    //测试代码
    DFSTraverse(G);
    cout << "The Inverse Topological Sequence is:\n";
    for (int i = 0; i < count; i++)
        cout << print[i] << ' ';

    return 0;
}